import {scan} from './LexParser.js'

//构建语法树
// 定义语法规则数据
let syntax = {
  Program: [["StatementList","EOF"]],
  StatementList: [
    ["Statement"],
    ["StatementList","Statement"]
  ],
  Statement: [
    ["ExpressionStatement"],
    ["IfStatement"],
    ["VariableDeclaration"],
    ["FunctionDeclaration"]
  ],
  IfStatement: [
    ["if", "(","Expression",")","Statement"]
  ],
  VariableDeclaration:[
    ["var", "Identifier",";"],
    ["let", "Identifier",";"],
  ],
  FunctionDeclaration:[
    ["function", "Identifier", "(",")","{","StatementList","}"]
  ],
  ExpressionStatement:[
    ["Expression",";"]
  ],
  Expression:[
    ["AssignmentExpression"],
  ],
  AssignmentExpression:[
    ["LeftHandsideExpression", "=" , "LogicalORExpression"],
    ["LogicalORExpression"]
  ],
  LogicalORExpression:[
    // 总是放优先级最低的运算,再层层深入
    ["LogicalORExpression", "||" , "LogicalANDExpression"],
    ["LogicalANDExpression"]
  ],
  LogicalANDExpression:[
    ["AdditiveExpression"],
    ["LogicalANDExpression", "&&" , "AdditiveExpression"],
  ],
  AdditiveExpression: [
    ["MultiplicativeExpression"],
    ["AdditiveExpression", "+" , "MultiplicativeExpression"],
    ["AdditiveExpression", "-" , "MultiplicativeExpression"],
  ],
  MultiplicativeExpression: [
    ["LeftHandsideExpression"],
    ["MultiplicativeExpression","*", "LeftHandsideExpression"],
    ["MultiplicativeExpression","/","LeftHandsideExpression"],
  ],
  LeftHandsideExpression:[
    ["CallExpression"],
    ["MemberExpression"],
  ],
  CallExpression:[
    // new a()
    ["MemberExpression","Arguments"],
    ["CallExpression","Arguments"]
  ],
  // Arguments:[
  //   ["(",")"],
  //   ["(","ArgumentList",")"]
  // ],
  // ArgumentLists:[
  //   ["AssignmentExpression"],
  //   ["ArgumentList","AssignmentExpression"]
  // ],
  NewExpression:[
    // new a
    ["MemberExpression"],
    ["new","NewExpression"],
  ],
  MemberExpression:[
    // new a.b()
    ["PrimaryExpression"],
    ["PrimaryExpression",".","Identifier"],
    ["PrimaryExpression","[","Expression","]"]
  ],
  PrimaryExpression:[
    ["(", "Expression", ")"],
    ["Literal"],
    ["Identifier"]
  ],
  Literal: [
    ["NumbericLiteral"],
    ["StringLiteral"],
    ["BooleanLiteral"],
    ["NullLiteral"],
    ["RegularExpressionLiteral"],
    ["ObjectLiteral"],
    ["ArrayLiteral"]
  ],
  ObjectLiteral:[
    ["{","}"],
    ["{","PropertyList","}"],
  ],
  PropertyList:[
    ["Property"],
    ["PropertyList" ,",","Property"],
  ],
  Property:[
    ["StringLiteral", ":", "AdditiveExpression"],
    ["Identifier", ":", "AdditiveExpression"]
  ],
  
}

//使用hash去去除重复节点
let hash = {
}

/**
 * 广度优先搜索获取token
 */
function closure(state){
  hash[JSON.stringify(state)] = state
  //广度优先搜索
  let queue = []
  for(let symbol in state){
    if(symbol.match(/^\$/)){
      continue
    }
    queue.push(symbol);
  }
  while(queue.length){
    let symbol = queue.shift();
    // console.log(symbol);
    if(syntax[symbol]){
      
      for(let rule of syntax[symbol]){
        if(!state[rule[0]]){
          queue.push(rule[0])
        }
        // state[rule[0]] = true
        // 遍历变成可以做状态迁移的state
        let current = state;
        for(let part of rule){
          if(!current[part]){
            current[part] = {}
          }
          current = current[part]
        }
        // current.$isRuleEnd = true
        current.$reduceType = symbol
        current.$reduceLenth = rule.length
      }
    }
  }

  for(let symbol in state){
    if(symbol.match(/^\$/)){
      continue
    }
    // console.log(symbol)
    if(hash[JSON.stringify(state[symbol])]){
      state[symbol] = hash[JSON.stringify(state[symbol])]
    } 
    else 
      closure(state[symbol])
  }
}

let end = {
  $isEnd: true
}

let start = {
  "Program": end
}



closure(start)
// console.log(start)


export function parse(source){
  let stack = [start]
  let symbolStack = []
  function reduce(){
    let state = stack[stack.length -1];
    if(state.$reduceType) {
      let children = []
      for (let i=0; i< state.$reduceLenth; i++){
        // children.push(stack.pop());
        stack.pop()
        children.push(symbolStack.pop())
      }
      //create non-terminal symbol and shift it
      return {
        type: state.$reduceType,
        children: children.reverse()
      }
    } 
  }

  function shift(symbol){
    let state = stack[stack.length -1];
    // console.log(symbol)
    if(symbol.type in state){
      stack.push(state[symbol.type]);
      symbolStack.push(symbol)
    } else {
      /*reduce to non-terminal symbols */
      shift(reduce())
      shift(symbol)
    }
  }

  for(let symbol/*terminal symbols */ of scan(source)) {
    shift(symbol);
  }

  return reduce();
}




////////////////////////////////////
// let source = `
//   var a;
// `
// let tree = parse(source);
// console.log(tree)
// evaluate(tree)

// window.js = {
//   evaluate, parse
// }